a) look at this (page 2): http://www2.ee.ntu.edu.tw/~yen/courses/al-03/HW2sol.pdf




b) look at this (page 2): part c http://www2.ee.ntu.edu.tw/~yen/courses/al-03/HW2sol.pdf



c) 

c is the denominations array 


findMinCoins(int n, int[] c){
	int[] solns = new int[n]; // filled with -1s 
	return recursFind(n,c,solns);
} 

recursFind(int n; int[] c, int[] solns){
	
	if(n<0) return infinity; 
	if (n==0) return 0;

	if(solns[n]<0){//haven't solved this subproblem yet
		int minCoinsForN=infinity //need to initalize
		for(int i=1; i<=c.length; i++){//using 1 indexing
			minCoinsForN=min(minCoinsForN,recursFind(n-c[i],c,solns))
			solns[n]=1+minCoinsForN;
		}
	}
	return solns[n] //here's the dynamic 
	//programming bit: we don't calculate 
	//subproblems that we've already computed
}

invariant: look at invariant tomorrow. 








2.